package main

import (
	"bytes"
	"fmt"
	"os"
	"strings"
)

func main() {
	results := permutations([]string{"a", "b", "c", "d", "e"}, 5, false)

	resultItems := make([]string, 0, len(results))
	for _, result := range results {
		resultItems = append(resultItems, strings.Join(result, ","))
	}

	buff := bytes.NewBufferString("")
	resultItemsSlice := permutations(resultItems, 5, true)
	for _, item := range resultItemsSlice {
		fmt.Println(strings.Join(item, "|"))
		buff.WriteString(strings.Join(item, "|"))
		buff.WriteString("\n")
	}
	if err := os.WriteFile("result.txt", buff.Bytes(), 0644); err != nil {
		panic(err)
	}

	fmt.Println(len(resultItemsSlice))
}

func permutations(items []string, size int, cutBranch bool) [][]string {
	results := make([][]string, 0)
	itemSet := make(map[string]bool)
	resultSet := make(map[string]bool)
	count := 0

	var f func(curItems []string)
	f = func(curItems []string) {
		if len(curItems) > 1 && cutBranch {
			if isNeedCutBranch(curItems) {
				return
			}
		}

		if len(curItems) == size {
			result := strings.Join(curItems, "|")
			if resultSet[result] {
				return
			}

			count++
			fmt.Println(count, result)
			results = append(results, append([]string{}, curItems...))
			resultSet[result] = true
			return
		}

		for _, item := range items {
			if itemSet[item] {
				continue
			}

			itemSet[item] = true
			f(append(curItems, item))
			itemSet[item] = false
		}
	}
	f([]string{})

	return results
}

func isNeedCutBranch(itemsPermutations []string) bool {
	itemIndexSet := make(map[string]map[int]bool)
	doubleSet := make(map[string]bool)

	for _, items := range itemsPermutations {
		itemSlice := strings.Split(items, ",")
		double := itemSlice[3] + "," + itemSlice[4]
		if doubleSet[double] {
			return true
		}

		doubleSet[double] = true
		doubleSet[itemSlice[4]+","+itemSlice[3]] = true

		for i, item := range itemSlice {
			if _, ok := itemIndexSet[item]; !ok {
				itemIndexSet[item] = make(map[int]bool)
			}

			if itemIndexSet[item][i] {
				return true
			}

			itemIndexSet[item][i] = true
		}
	}

	return false
}
